YES 1.601
H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:
↳ HASKELL
↳ BR
mainModule Main
| ((encodeFloat :: Integer -> Int -> Float) :: Integer -> Int -> Float) |
module Main where
Replaced joker patterns by fresh variables and removed binding patterns.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
mainModule Main
| ((encodeFloat :: Integer -> Int -> Float) :: Integer -> Int -> Float) |
module Main where
Cond Reductions:
The following Function with conditions
is transformed to
undefined0 | True | = undefined |
undefined1 | | = undefined0 False |
The following Function with conditions
power | vw 0 | = 1.0 |
power | x vx@(y+1) | = fromInt x * power x y |
power | x y | = 1.0 / power x (`negate` y) |
is transformed to
power | vw xu | = power4 vw xu |
power | x vx | = power2 x vx |
power | x y | = power0 x y |
power0 | x y | = 1.0 / power x (`negate` y) |
power1 | True x vx | = fromInt x * power x (vx - 1) |
power1 | wv ww wx | = power0 ww wx |
power2 | x vx | = power1 (vx >= 1) x vx |
power2 | wy wz | = power0 wy wz |
power3 | True vw xu | = 1.0 |
power3 | xv xw xx | = power2 xw xx |
power4 | vw xu | = power3 (xu == 0) vw xu |
power4 | xy xz | = power2 xy xz |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
mainModule Main
| ((encodeFloat :: Integer -> Int -> Float) :: Integer -> Int -> Float) |
module Main where
Let/Where Reductions:
The bindings of the following Let/Where expression
fromInteger x * power 2 y |
where |
power | vw xu | = power4 vw xu |
power | x vx | = power2 x vx |
power | x y | = power0 x y |
|
|
power0 | x y | = 1.0 / power x (`negate` y) |
|
|
power1 | True x vx | = fromInt x * power x (vx - 1) |
power1 | wv ww wx | = power0 ww wx |
|
|
power2 | x vx | = power1 (vx >= 1) x vx |
power2 | wy wz | = power0 wy wz |
|
|
power3 | True vw xu | = 1.0 |
power3 | xv xw xx | = power2 xw xx |
|
|
power4 | vw xu | = power3 (xu == 0) vw xu |
power4 | xy xz | = power2 xy xz |
|
are unpacked to the following functions on top level
primFloatEncodePower1 | True x vx | = fromInt x * primFloatEncodePower x (vx - 1) |
primFloatEncodePower1 | wv ww wx | = primFloatEncodePower0 ww wx |
primFloatEncodePower3 | True vw xu | = 1.0 |
primFloatEncodePower3 | xv xw xx | = primFloatEncodePower2 xw xx |
primFloatEncodePower4 | vw xu | = primFloatEncodePower3 (xu == 0) vw xu |
primFloatEncodePower4 | xy xz | = primFloatEncodePower2 xy xz |
primFloatEncodePower0 | x y | = 1.0 / primFloatEncodePower x (`negate` y) |
primFloatEncodePower | vw xu | = primFloatEncodePower4 vw xu |
primFloatEncodePower | x vx | = primFloatEncodePower2 x vx |
primFloatEncodePower | x y | = primFloatEncodePower0 x y |
primFloatEncodePower2 | x vx | = primFloatEncodePower1 (vx >= 1) x vx |
primFloatEncodePower2 | wy wz | = primFloatEncodePower0 wy wz |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
mainModule Main
| ((encodeFloat :: Integer -> Int -> Float) :: Integer -> Int -> Float) |
module Main where
Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
mainModule Main
| (encodeFloat :: Integer -> Int -> Float) |
module Main where
Haskell To QDPs
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_primPlusNat(Succ(yu700), Succ(yu60000)) → new_primPlusNat(yu700, yu60000)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primPlusNat(Succ(yu700), Succ(yu60000)) → new_primPlusNat(yu700, yu60000)
The graph contains the following edges 1 > 1, 2 > 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_primMulNat(Succ(yu3000), Succ(yu6000)) → new_primMulNat(yu3000, Succ(yu6000))
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primMulNat(Succ(yu3000), Succ(yu6000)) → new_primMulNat(yu3000, Succ(yu6000))
The graph contains the following edges 1 > 1, 2 >= 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
new_primFloatEncodePower(Pos(Succ(Succ(yu4000)))) → new_primFloatEncodePower(Pos(Succ(yu4000)))
new_primFloatEncodePower(Pos(Succ(Zero))) → new_primFloatEncodePower(Pos(Zero))
new_primFloatEncodePower(Neg(Succ(yu400))) → new_primFloatEncodePower(Pos(Succ(yu400)))
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 2 less nodes.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ RuleRemovalProof
Q DP problem:
The TRS P consists of the following rules:
new_primFloatEncodePower(Pos(Succ(Succ(yu4000)))) → new_primFloatEncodePower(Pos(Succ(yu4000)))
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the rule removal processor [15] with the following polynomial ordering [25], at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
Strictly oriented dependency pairs:
new_primFloatEncodePower(Pos(Succ(Succ(yu4000)))) → new_primFloatEncodePower(Pos(Succ(yu4000)))
Used ordering: POLO with Polynomial interpretation [25]:
POL(Pos(x1)) = 2·x1
POL(Succ(x1)) = 1 + 2·x1
POL(new_primFloatEncodePower(x1)) = 2·x1
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ RuleRemovalProof
↳ QDP
↳ PisEmptyProof
Q DP problem:
P is empty.
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.